package algorithms.a07graphBasics;

import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;

import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * 寻路
 * 一个图中的一个点对应一个对象
 *
 * @author 王昊然
 * @create 2018-03-05 8:45
 **/
public class ShortestPath {
    private Graph g;
    private int s;
    private boolean[] visited;
    private int[] from; //from[i]存储坐标i路径上对应的前一个点

    public ShortestPath(Graph g, int s) {
        Preconditions.checkArgument(s >= 0 && s < g.V(), "s值超出范围！");

        this.g = g;
        this.s = s;

        visited = new boolean[g.V()];
        from = new int[g.V()];

        for (int i = 0; i < visited.length; i++) {
            from[i] = -1;
        }

        bfs(s);
    }

    private void bfs(int s) {
        List<Integer> list = Lists.newLinkedList();
        list.add(s);
        visited[s] = true;

        while(!list.isEmpty()){
            Integer v = list.remove(0);
            Iterator<Integer> iterator = g.adj(s).iterator();
            while (iterator.hasNext()) {
                Integer next = iterator.next();
                if (!visited[next]) {
                    from[next] = v;
                    list.add(next);
                    visited[next] = true;
                }
            }
        }
    }

    public boolean hashPath(int w) {
        Preconditions.checkArgument(w >= 0 && w < g.V(), "w参数值不正确！");
        return visited[w];
    }

    public List<Integer> path(int w) {
        Preconditions.checkArgument(w >= 0 && w < g.V(), "w参数值不正确！");
        Stack stack = new Stack();
        stack.push(w);
        while (from[w] != -1) {
            stack.push(from[w]);
            w = from[w];
        }

        List<Integer> list = Lists.newArrayList();
        while (!stack.isEmpty()) {
            list.add((Integer) stack.pop());
        }

        return list;
    }

    public void showPath(int w) {
        if (!hashPath(w)) System.out.println("无相关路径信息");

        List<Integer> vList = path(w);

        System.out.println("路径信息如下：");
        for (Integer i : vList) {
            System.out.print(i + " ");
        }
    }


    // 测试寻路算法
    public static void main(String[] args) {

        String filename = "testG.txt";
        SparseGraph g = new SparseGraph(7, false);
        ReadGraph readGraph = new ReadGraph(g, filename);
        g.show();
        System.out.println();

        Path path1 = new Path(g, 0);
        System.out.println("Path from 0 to 6 : ");
        path1.showPath(6);
        System.out.println();

        ShortestPath path = new ShortestPath(g, 0);
        System.out.println("ShortestPath from 0 to 6 : ");
        path.showPath(6);
    }
}

